import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 26
 * Time: 19:48
 */
//牛客 二叉树的前序遍历
class TreeNode {
    int val = 0;
   TreeNode left = null;
    TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
}
public class Solution3 {
    //法一 官方推荐方法
    public List<Integer> preorder(TreeNode root){
        List<Integer> list = new ArrayList<>();//递归有返回值时，顺序表定义在这个递归函数的里面。递归没有返回值时，顺序表定义在这个递归函数的外面
        if(root == null) return list;
        list.add(root.val);
        List<Integer> list1 = preorder(root.left);
        list.addAll(list1);
        List<Integer> list2 = preorder(root.right);
        list.addAll(list2);
        return list;
    }
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = preorder(root);
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    //法二 官方方法
    public int[] preorderTraversal1 (TreeNode root) {
        if(root == null) return new int[0];
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {//条件是!stack.isEmpty()
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}
